contents

세그먼트 트리(Segment Tree) 는 배열에 대한 구간 쿼리(range query) 를 효율적으로 처리할 수 있는 다재다능한 트리 기반의 자료구조입니다. 이 자료구조의 가장 큰 강점은 구간 쿼리와 점 업데이트(point update)를 모두 로그 시간 복잡도(O(logn))에 처리할 수 있다는 점으로, 동적 배열 문제에서 단순한 접근법보다 훨씬 뛰어난 성능을 보입니다.

문제점: 구간 쿼리

숫자 배열이 있고, 이 배열에 대해 두 가지 연산을 자주 수행해야 한다고 상상해 보세요.

1. 쿼리: 주어진 구간 [l, r](인덱스 l부터 r까지)의 원소 합을 구합니다.

2. 업데이트: 특정 인덱스 i의 원소 값을 변경합니다.

일반적인 접근법과 그 한계를 살펴보겠습니다.

• 단순한 접근법: 각 쿼리마다 l부터 r까지 반복문을 돌며 합을 구합니다.

  • 쿼리 시간: O(n)

  • 업데이트 시간: O(1)

  • 문제점: 쿼리가 많을 경우 너무 느립니다.

• 구간 합 배열 (Prefix Sum Array): prefix[i]가 0부터 i까지의 모든 원소 합을 저장하는 배열을 미리 계산해 둡니다. 그러면 [l, r] 구간의 합은 prefix[r] - prefix[l-1]로 구할 수 있습니다.

  • 쿼리 시간: O(1)

  • 업데이트 시간: O(n) (원소 하나가 업데이트되면 그 뒤의 모든 구간 합을 다시 계산해야 합니다.)

  • 문제점: 정적인 배열에는 훌륭하지만, 원소 변경이 잦으면 끔찍한 성능을 보입니다.

바로 이 지점에서 세그먼트 트리가 등장합니다. 세그먼트 트리는 균형 잡힌 해결책을 제공합니다.

• 세그먼트 트리:

  • 쿼리 시간: O(logn)

  • 업데이트 시간: O(logn)

  • 해결책: 동적 데이터에 대한 빠른 쿼리가 필요한 애플리케이션에 완벽합니다.

세그먼트 트리의 구조 🌳

세그먼트 트리는 배열 위에 구축되는 완전 이진 트리(full binary tree) 입니다.

• 리프 노드 (Leaves): 트리의 리프 노드들은 원본 배열의 개별 원소를 나타냅니다. 크기 n의 배열에 대해 n개의 리프 노드가 있습니다.

• 내부 노드 (Internal Nodes): 각 내부 노드는 자식 노드들이 나타내는 구간의 집계 정보(합, 최솟값, 최댓값 등)를 저장합니다. 예를 들어, 구간 합 세그먼트 트리에서 내부 노드는 왼쪽 자식과 오른쪽 자식의 합을 저장합니다.

예시:

배열 A = [2, 5, 1, 4, 9, 3]을 생각해 봅시다. 구간 합에 대한 세그먼트 트리는 다음과 같은 형태가 됩니다.

• 루트 노드는 전체 배열 [0...5]의 합인 24를 나타냅니다.

• 그 자식들은 각각 [0...2]의 합(8)과 [3...5]의 합(16)을 나타냅니다.

• 이 과정은 개별 배열 원소를 저장하는 리프 노드에 도달할 때까지 계속됩니다.

생성 방법

세그먼트 트리는 보통 이진 힙(binary heap)처럼 배열을 사용하여 구현됩니다. 만약 어떤 노드가 인덱스 i에 있다면, 그 왼쪽 자식은 2*i + 1, 오른쪽 자식은 2*i + 2에 위치합니다. 트리를 저장하는 데 필요한 배열의 크기는 안전하게 4n 정도로 잡습니다.

트리는 재귀적으로 생성됩니다.

build(node_index, start, end) 함수:

1. 기저 조건 (Base Case): start == end이면, 리프 노드에 도달한 것입니다. tree[node_index] = array[start]로 설정합니다.

2. 재귀 단계 (Recursive Step):

   • 중간 지점을 계산합니다: mid = (start + end) / 2.

   • 왼쪽 자식에 대해 [start, mid] 구간을 처리하도록 build 함수를 재귀적으로 호출합니다.

   • 오른쪽 자식에 대해 [mid + 1, end] 구간을 처리하도록 build 함수를 재귀적으로 호출합니다.

   • 현재 노드의 값은 자식 노드들의 값을 조합하여 결정됩니다: tree[node_index] = tree[left_child] + tree[right_child].

초기 호출은 build(0, 0, n-1)입니다. 전체 생성 과정은 트리의 각 노드를 정확히 한 번씩 방문하므로 O(n) 의 시간이 걸립니다.

연산

1. 구간 쿼리: query(l, r)

세그먼트 트리의 강력함은 모든 원소를 방문하지 않고도 [l, r] 구간에 대한 쿼리에 답할 수 있다는 점입니다. 쿼리 함수는 현재 노드가 담당하는 구간 [start, end]와 쿼리 구간 [l, r]의 관계를 세 가지 경우로 나누어 재귀적으로 동작합니다.

query(node_index, start, end, l, r) 함수:

• Case 1: 겹치지 않는 경우 (No Overlap). 노드의 구간 [start, end]가 쿼리 구간 [l, r]의 밖에 완전히 벗어난 경우입니다.

  • if (start > r or end < l)

  • 이 경우, 해당 노드의 구간은 쿼리에 아무런 기여를 하지 않습니다. 항등원 값(합의 경우 0, 최솟값의 경우 +∞, 최댓값의 경우 −∞)을 반환합니다.

• Case 2: 완전히 포함되는 경우 (Total Overlap). 노드의 구간 [start, end]가 쿼리 구간 [l, r] 안에 완전히 포함되는 경우입니다.

  • if (start >= l and end <= r)

  • 더 깊이 들어갈 필요가 없습니다. 이 노드에 미리 계산된 값이 바로 쿼리의 일부로 필요한 값입니다. tree[node_index]를 반환합니다.

• Case 3: 부분적으로 겹치는 경우 (Partial Overlap). 노드의 구간이 쿼리 구간과 부분적으로 겹치는 경우입니다.

  • 왼쪽과 오른쪽 자식에 대해 쿼리 함수를 재귀적으로 호출합니다.

  • 그 결과들을 조합하여 값을 반환합니다(예: query(left_child, ...) + query(right_child, ...)).

이 과정은 매우 효율적입니다. 트리의 각 레벨에서 쿼리 경로는 멈추거나(완전 포함) 계속 내려갑니다. 경로는 최대 한 번만 두 갈래로 나뉠 수 있습니다. 트리의 높이가 $O(\log n)$이므로, 쿼리 시간은 **O(logn)**입니다.

2. 점 업데이트: update(index, value)

원본 배열의 한 원소를 업데이트하려면, 세그먼트 트리에서 그에 해당하는 노드들도 업데이트해야 합니다.

update(node_index, start, end, idx, val) 함수:

1. 기저 조건: start == end이면, 인덱스 idx에 해당하는 리프 노드를 찾은 것입니다. 그 값을 업데이트합니다: tree[node_index] = val.

2. 재귀 단계:

   • mid 지점을 찾습니다.

   • idx가 왼쪽 절반에 있는지 오른쪽 절반에 있는지 판단하여 적절한 자식에게 재귀 호출을 합니다.

   • 재귀 호출이 반환된 후, (업데이트되었을 수 있는) 자식 노드들의 값을 기반으로 현재 노드의 값을 다시 계산합니다: tree[node_index] = tree[left_child] + tree[right_child].

이 업데이트 과정은 루트에서 리프까지 단일 경로를 따라 내려갔다가 다시 올라옵니다. 트리의 높이가 $O(\log n)$이므로, 업데이트 시간 또한 **O(logn)**입니다.

심화 주제: Lazy Propagation

표준 세그먼트 트리는 점 업데이트에는 효율적입니다. 하지만 "인덱스 l부터 r까지 모든 원소에 5를 더하라"와 같은 구간 업데이트를 수행해야 한다면 어떨까요? 각 점을 개별적으로 업데이트하는 것은 너무 느릴 것입니다($O(nlogn)$).

Lazy Propagation은 이 문제를 해결하는 기법입니다. 아이디어는 업데이트를 지연시키는 것입니다. 구간 업데이트가 어떤 노드의 전체 구간을 포함할 때, 그 자식들을 모두 업데이트하는 대신, 해당 노드에 "게으른(lazy)" 태그를 저장하여 보류 중인 업데이트가 있음을 표시합니다. 그리고 꼭 필요할 때(즉, 후속 쿼리나 업데이트가 자식 노드에 접근해야 할 때)에만 이 업데이트를 아래로 "전파(propagate)"합니다.

Lazy Propagation을 사용하면 구간 업데이트 또한 O(logn) 시간에 처리할 수 있습니다.

결론

세그먼트 트리는 경쟁 프로그래밍과 알고리즘 설계에서 매우 중요한 자료구조입니다. 구간 쿼리와 업데이트를 모두 효율적으로 수행하는 능력 덕분에, 구간에 대한 동적 데이터를 다루는 문제에 적합합니다. 주된 용도는 합을 구하는 것이지만, 구간 최솟값/최댓값, 곱, 최대공약수(GCD) 등 결합 법칙이 성립하는 모든 연산에 적용할 수 있습니다.

references